In many computer-based visualization systems, it is desirable to be able to define a skeleton or centerline through the object being viewed. Such a skeleton provides a reference path for virtual navigation, such as in virtual colonoscopy. Similarly, accurate length measurements and navigation through other organs, such as the aorta, also require an object skeleton. Of course, the need to define an accurate centerline or tree is not limited to medical imaging. Other fields, such as virtual engineering and architecture would also benefit from accurate methods of defining a skeleton in tree like objects or generating a centerline in linear objects in various visualization applications.
Various techniques are known for generating a center line for an object being visualized. For example, in the virtual examination of organs, such as the colon, a centerline can be manually marked by the radiologist while reviewing image data, such as CT, MRI or ultrasound data. However, because of the high level of manual intervention involved in this technique, it is expensive and generally not preferred.
An automatic method of generating a centerline is referred to as topological thinning, or “onion peeling.” While there are numerous known variants of this technique, in general, volume units (voxels) from a region of interest are removed layer by layer from the boundary until what remains is a connected line of predetermined thickness, such as one voxel. While this technique has generally proven effective at determining a centerline in objects such as the colon, it has the disadvantage of being computationally expensive. In addition, with certain geometry's, the centerline that is determined by topological thinning is not always the centerline which would be intuitively desired.
Other techniques for generating a centerline through a virtual object include the use algorithms which attempt to determine the shortest path through an object, such as the Dijkstra algorithm, which is disclosed in the article “A Note on Two Problems in Connexion with Graphs,” Dijkstra, Numerishe Mathemetik, vol. 1, pp 269-271, 1959, which is hereby incorporated by reference in its entirety. The Dijkstra algorithm finds the global minimal weight path in a weighted graph with nonnegative weights. This algorithm generally includes two phases: first, a distance from a source field (DSF) is created by labeling all graph vertices with the shortest distance from a single source to those vertices. Second, the shortest path is determined by tracing back from the farthest node to the source node. Thus, use of this algorithm requires mapping the image data to a graph form. An example of such a mapping is illustrated in FIG. 8a. The Dijkstra algorithm has a draw back in the case of sharp turns occurring in the object. In such as case, the algorithm in seeking the shortest path tends to “hug the corner” and the centerline shifts from the center towards the boundary.
A skeleton of a virtual object can be defined in the context of a number of desired properties. As used herein, a skeleton should be tree-shaped and composed of single voxel paths through the branches. Thus, the skeleton represents a 1D curve in a 3D space rather than a 2D manifold. The skeleton should remain within the boundary of the region of interest and more preferably should remain in the “center” of the shape. For objects of arbitrary form, the concept of center may require a balancing between maximizing the distance from all of the boundaries of the boundaries of the region of interest and minimizing the extent that the centerline takes on a tortuous path. This balancing implies the desirability of applying a form of shortest path or union of shortest paths in deriving a skeleton.
Although a number of techniques are known for generating a skeleton of an object, each of the known techniques have inherent drawbacks. Thus, there remains a need for improved techniques for generating centerlines, skeletons and or navigation paths within virtual objects.
The centerline is often used as the primary path for navigating through a virtual object. For example, in the case of virtual colonoscopy, the user is generally allowed to navigate along the centerline of the colon in either direction and can navigate off the centerline to explore regions of interest. Thus, virtual colonoscopy can provide the viewer with a more flexible view of the inner luminal surface of the colon than can be achieved with conventional optical colonoscopy. This is accomplished due to the fact that virtual reality and computer graphics allow the virtual camera to view from any arbitrary viewpoint and with any arbitrary view-direction, while optical colonoscopy is limited to a path in one direction along the colon (due to the fact that the optical camera is placed at the end of a probe with limited mobility). However, with the flexibility that is provided by virtual examination comes a new challenge. Specifically, the difficulty in following orientation changes. The colon is a very tortuous organ, and, as a result, when following along the colon in 3D users can become disoriented. This risk is especially present when the user veers off the centerline and examines a structure close to the colon wall. Often times, when returning to the centerline, the user may head back in the direction they previously came from. Since the view is from the opposite direction, it is usually not readily apparent that the flight is headed in the reverse direction. Thus it would be desirable to provide a method of reducing the opportunity for a viewer to become disoriented while navigating through the virtual object without reducing the desirable flexibility which can be achieved in the virtual environment.